package org.TheSubject;

import java.util.*;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * 有效括号组合需满足：左括号必须以正确的顺序闭合。
 * 输入：n = 1
 * 输出：["()"]
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 */
public class Solution22OfHot {
    public List<String> generateParenthesis(int n) {
        if (n == 1) {
            return Arrays.asList("()");
        }
        Set<String> hs = new HashSet<>();
        for (String s : generateParenthesis(n-1)) {
            for (int i = 0; i < 2*n-2; i++) {
                hs.add(s.substring(0,i) + "()" + s.substring(i,s.length()));
            }
        }
        return new ArrayList(hs);
    }

    /**
     *  private List<String> resultList;
     *     private StringBuilder result;
     *     private int maxSize;
     *     private int size;
     *     public List<String> generateParenthesis(int n) {
     *               resultList=new ArrayList<>();
     *         if(n==1){
     *             resultList.add("()");
     *             return resultList;
     *         }
     *         maxSize=2*n;
     *         size=n;
     *         result=new StringBuilder(maxSize);
     *         backtrack(0,0);
     *         return resultList;
     *     }
     *     public void backtrack(int left,int right){
     *         if(result.length()==maxSize){
     *             resultList.add(result.toString());
     *             return;
     *         }
     *         if(left<size){
     *             result.append("(");
     *             backtrack(left+1,right);
     *             result.deleteCharAt(result.length()-1);
     *         }
     *         if(right<left){
     *             result.append(")");
     *             backtrack(left,right+1);
     *             result.deleteCharAt(result.length()-1);
     *         }
     *     }
     * @param args
     */
    public static void main(String[] args) {
        Solution22OfHot solution22OfHot = new Solution22OfHot();
        System.out.println(solution22OfHot.generateParenthesis(2));
    }
}
